Scroll Progress Bar

Insertion sort

Insertion sort is another simple sorting algorithm that builds the final sorted array one item at a time. It works by repeatedly taking an unsorted element and inserting it into its correct position in the sorted part of the array. Here's how it can implement insertion sort in C++:

Program:

#include <iostream>

void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int key = arr[i];
        int j = i - 1;

        // Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original array: ";
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }

    insertionSort(arr, size);

    std::cout << "\nSorted array: ";
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }

    return 0;
}
In this code:
  • insertionSort is a function that takes an array arr and its size size as parameters and sorts the array in ascending order using the insertion sort algorithm.
  • The outer loop (with index i) iterates through the array starting from the second element (index 1) to the end.
  • In each iteration of the outer loop, the current element arr[i] is compared with the elements to its left in the sorted portion of the array (from arr[0] to arr[i-1]).
  • If an element to the left of arr[i] is greater, it is moved one position to the right to make space for arr[i].
  • This process continues until the correct position for arr[i] is found, and it is inserted into that position.
When run this code, it will sort the arr array in ascending order using insertion sort and print both the original and sorted arrays. Here's a Sample Output:
Program:

Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90

As it can see, the array is sorted in ascending order after applying the insertion sort algorithm.


question

answer

question2

answer2